//Given a string, your task is to count how many palindromic substrings in this 
//string. 
//
// The substrings with different start indexes or end indexes are counted as dif
//ferent substrings even they consist of same characters. 
//
// Example 1: 
//
// 
//Input: "abc"
//Output: 3
//Explanation: Three palindromic strings: "a", "b", "c".
// 
//
// 
//
// Example 2: 
//
// 
//Input: "aaa"
//Output: 6
//Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
// 
//
// 
//
// Note: 
//
// 
// The input string length won't exceed 1000. 
// 
//
// Related Topics 字符串 动态规划


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    fun countSubstrings(s: String): Int {
        var result = 0
        for (i in 0 until s.length){
            result++
            for (j in i+1 until s.length) {
                if (check(s, i, j)) {
                    result++
                }
            }
        }
        return result
    }

    fun check(s: String, start: Int, end: Int): Boolean {
        var i = start
        var j = end

        while (i < j){
            if(s[i] != s[j]){
                return false
            }
            i++
            j--
        }

        return true
    }
}
//leetcode submit region end(Prohibit modification and deletion)
